Problem

Time limit : 3sec / Memory limit : 256MB

题意：

给出$n$个数，其中有一个数会出现两次，其余数只出现一次，问不同长度且不同的子串的数量。取模$10^9+7$

Solution

简单容斥。求出所有情况,减去重复情况.

Code:

Click to show/hide the code

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef double DB;
typedef unsigned int UI;
typedef pair<int, int> PII;

const int inf = 0x7f7f7f7f;

#define rdi() read<int>()
#define rdl() read<LL>()
#define rds(a) scanf("%s", a)
#define mk(i, j) make_pair(i, j)
#define pb push_back
#define fi first
#define se second
#define For(i, j, k) for (int i = j; i <= k; i ++)
#define Rep(i, j, k) for (int i = j; i >= k; i --)
#define Edge(i, u) for (int i = head[u]; i; i = e[i].nxt)

template<typename t> t read()
{
    t x = 0; int f = 1; char c = getchar();
    while (c > '9' || c < '0') f = c == '-' ? -1 : 1 , c = getchar();
    while (c >= '0' && c <= '9') x = x * 10 + c - 48 , c = getchar();
    return x * f;
}

template<typename t> void write(t x)
{
    if (x < 0){
        putchar('-'), write(-x);
        return;
    }
    if (x >= 10) write(x / 10);
    putchar(x % 10 + 48);
}

const int P = 1e9 + 7;
const int N = 1e5 + 10;
int fac[N], facinv[N], a[N], n, pos, vis[N], id;

int power(int a, int b)
{
    int c = 1;
    for (; b; b >>= 1, a = 1ll * a * a % P) if (b & 1) c = 1ll * c * a % P;
    return c;
}

int C(int x, int y)
{
    return 1ll * fac[x] * facinv[y] % P * facinv[x - y] % P;
}

int main()
{
    n = rdi() + 1;
    for (int i = 1; i <= n; i ++) a[i] = rdi();
    fac[0] = fac[1] = 1;
    for (int i = 2; i <= n; i ++) fac[i] = 1ll * fac[i - 1] * i % P;
    facinv[n] = power(fac[n], P - 2);
    for (int i = n - 1; i >= 0; i --) facinv[i] = 1ll * facinv[i + 1] * (i + 1) % P;
    for (int i = 1; i <= n; i ++)
	{
        if (vis[a[i]]) {
            pos = i;
            id = a[i];
            break;
        }
        vis[a[i]] = i;
    }
    int len = n - pos + 1;
    for (int i = 1; i <= n; i ++)
	{
        int ans = C(n, i); 
        if (i - 1 <= len - 1 + vis[id] - 1) ans -= C(len - 1 + vis[id] - 1, i - 1);
        ans = (ans + P) % P;
        write(ans), putchar(10);
    } 
    return 0;
}